package com.airport.schedule;

import com.airport.schedule.model.Flight;
import com.airport.schedule.model.FlightGate;
import com.airport.schedule.util.ListUtil;
import com.airport.schedule.util.SetUtil;
import edu.stanford.nlp.util.IntervalTree;

import java.util.*;


public class Problem {

    private List<Flight> scheduleFlights; // 该问题中所有待调度的航班
    private Set<Flight> noRegularGateFlights;  //  必须采取临时措施的航班
    private List<FlightGate> scheduleGates; //  该问题中所有可调度的机位
    private List<FlightGate> normalGates; // 正常的机位
    private List<FlightGate> adHocGates; // 采取临时措施的机位
    private Map<String,FlightGate> id2FlightGate;
    private Map<FlightGate, Set<FlightGate>> normalFlightGate2AdHocGate;
    private Map<FlightGate, Set<FlightGate>> adHocGate2AdHocGates;

    private String date;

    public Problem(Collection<Flight> flights, Collection<FlightGate> gates) {
        this.scheduleGates = new ArrayList<>(gates);
        this.scheduleFlights = new ArrayList<>(flights);
        this.normalGates = ListUtil.filter(scheduleGates, g->!g.isAdHocGate());
        this.adHocGates = ListUtil.filter(scheduleGates, FlightGate::isAdHocGate);
        this.noRegularGateFlights = new HashSet<>();
        this.id2FlightGate = new HashMap<>();
        gates.forEach(g->id2FlightGate.put(g.getFlightGateId(),g));
        this.normalFlightGate2AdHocGate = new HashMap<>();
        this.adHocGate2AdHocGates = new HashMap<>();
    }

    public Problem(Collection<Flight> flights, Collection<FlightGate> gates, String date) {
        this(flights, gates);
        this.date = date;
    }

    public void preProcess() {
        for(FlightGate normal : normalGates) {
            for(FlightGate adHoc : adHocGates) {
                if(adHoc.getRule().affect(normal)) {
                    Set<FlightGate> adGates = normalFlightGate2AdHocGate.getOrDefault(normal, new HashSet<>());
                    adGates.add(adHoc);
                    normalFlightGate2AdHocGate.put(normal, adGates);
                }
            }
        }
        for(FlightGate a1 : adHocGates) {
            for(FlightGate a2 : adHocGates) {
                if(a1 != a2) {
                    if(a2.getRule().affect(a1)) {
                        Set<FlightGate> adGates = adHocGate2AdHocGates.getOrDefault(a1, new HashSet<>());
                        adGates.add(a2);
                        adHocGate2AdHocGates.put(a1, adGates);
                    }
                }
            }
        }
    }

    public void desc() {
        normalFlightGate2AdHocGate.forEach((k, v)->{
            String ss = "";
            for(FlightGate g : v) {
                ss += g.getFlightGateId()+",";
            }
            System.out.println(k.getFlightGateId()+"==>>"+ss);
        });
        System.out.println("**********************************************");
        adHocGate2AdHocGates.forEach((k, v)->{
            String ss = "";
            for(FlightGate g : v) {
                ss += g.getFlightGateId()+",";
            }
            System.out.println(k.getFlightGateId()+"==>>"+ss);
        });
    }


    // 预先将必须采取临时措施的机位抽离出来
    public void preDecideNoRegularGateFlight() {
        final Map<Flight, List<FlightGate>> flightAvailableGates = getFlightAvailableGates(false);// 计算每个航班可能对应的机位
        noRegularGateFlights.addAll(ListUtil.filter(scheduleFlights,
                f->flightAvailableGates.get(f) == null));

        List<Flight> hasRegularGateFlights = ListUtil.filter(scheduleFlights, f->flightAvailableGates.get(f) != null);
        List<Flight> flightsToBeAnalyzed = new ArrayList<>(hasRegularGateFlights);
        IntervalTree<Integer, Flight> intervalTree = new IntervalTree<>();
        intervalTree.addAll(hasRegularGateFlights);

        final Map<String,Double> commonGateMap =
                getFlightCompeteGateRate(hasRegularGateFlights, intervalTree,flightAvailableGates);


        // 按照航班到达时间排序，先到的先分析
        Collections.sort(flightsToBeAnalyzed, (f1, f2)->f1.getArrivalTime()-f2.getArrivalTime());
         // 必然安排不到机位的航班
        while(!flightsToBeAnalyzed.isEmpty()) {
            Flight base = flightsToBeAnalyzed.remove(0);
            // 找出当前飞机场所有航班以及和base航班同时到来的航班
            List<Flight> currentAirportFlights = findAirportAndComingFlights(base, intervalTree);
            // 找出当前飞机场所有航班以及和base航班同时到来的航班中，与base航班有竞争关系的独立集合
            Set<Flight> independentFlights = new HashSet<>();
            independentFlights.add(base);
            Set<FlightGate> independentGates = new HashSet<>(flightAvailableGates.get(base));
            while(true) {
                int flightNum = independentFlights.size();
                for(Flight flight : currentAirportFlights) {
                    Set<FlightGate> gates = new HashSet<>(flightAvailableGates.get(flight));
                    if(SetUtil.hasIntersect(gates, independentGates)) {
                        independentFlights.add(flight);
                        independentGates.addAll(gates);
                    }
                }
                if(flightNum == independentFlights.size())
                    break;
            }
            // 将存在可能冲突的航班，进行预分配，找出比然冲突的航班
            List<Flight> conflictFlights = new ArrayList<>(independentFlights);
            Collections.sort(conflictFlights, (f1, f2)->{ // 将冲突航班按照每一个航班对应的机位数量进行从小到大排序
                int f1GateNum = flightAvailableGates.get(f1).size();
                int f2GateNum = flightAvailableGates.get(f2).size();
                return f1GateNum - f2GateNum;
            }); // 这一步至关重要，直接影响后续删除程序
            Set<Flight> mergedFlights = new HashSet<>();
            Set<FlightGate> mergedGates = new HashSet<>();
            for(int i = 0; i < conflictFlights.size(); i++) {
                Flight flight = conflictFlights.get(i);
                // 从合并集合中找出当前flight的额外机位
                Set<FlightGate> distinct = SetUtil.subtract(mergedGates,
                        new HashSet<>(flightAvailableGates.get(flight)));
                mergedFlights.add(flight);
                mergedGates.addAll(flightAvailableGates.get(flight));
                if(mergedGates.size() < mergedFlights.size()) { // 必然存在冲突，必须删除一个航班
                    List<Flight> candidates = new ArrayList<>(mergedFlights);
                    Map<Flight, Double> flight2Conflict = new HashMap<>();
                    for(Flight f : candidates) {
                        flight2Conflict.put(f,
                                computeFlightGateConflictRate(intervalTree, f, commonGateMap));
                    }
                    Collections.sort(candidates, (f1, f2)->{
                        int diff = Double.compare(flight2Conflict.get(f2), flight2Conflict.get(f1));
                        if(diff == 0) {
                            int gNum1 = flightAvailableGates.get(f1).size();
                            int gNum2 = flightAvailableGates.get(f2).size();
                            if(gNum1 == gNum2) {
                                int interval1 = f1.getDepartureTime() - f1.getArrivalTime();
                                int interval2 = f2.getDepartureTime() - f2.getArrivalTime();
                                return interval2 - interval1;
                            }
                            return gNum1-gNum2;
                        }
                        return diff;
                    });
                    for(Flight f : candidates) {
                        mergedGates.removeAll(distinct);
                        mergedFlights.remove(f);
                        if(mergedFlights.size() <= mergedGates.size()) { // 合法，可以删除
                            noRegularGateFlights.add(f);
                            flightsToBeAnalyzed.remove(f);
                            intervalTree.remove(f);
                            break;
                        }else{
                            mergedGates.addAll(distinct);
                            mergedFlights.add(f);
                        }
                    }
                }
            }
        }
        System.out.println("============严格理论分析该问题必然采取临时措施航班数量：" + noRegularGateFlights.size() + "===============================");
        scheduleFlights.removeAll(noRegularGateFlights);
        noRegularGateFlights.forEach(System.out::println);
        System.out.println("该问题调度航班数=" + scheduleFlights.size() + " 机位数=" + scheduleGates.size());
    }

    public Set<Flight> getNoRegularGateFlights() {
        return noRegularGateFlights;
    }

    public Map<Flight, List<FlightGate>> getFlightAvailableGates(boolean useAdHocGate) {
        Map<Flight, List<FlightGate>> flightAvailableGates = new HashMap<>(); // 计算每个航班可能对应的机位
        for(Flight flight : scheduleFlights) {
            scheduleGates.forEach(gate->{
                if(gate.acceptFlight(flight)) {
                    if(!useAdHocGate && gate.isAdHocGate()) return;
                    List<FlightGate> gates = flightAvailableGates.getOrDefault(flight, new ArrayList<>());
                    gates.add(gate);
                    flightAvailableGates.put(flight, gates);
                }
            });
        }
        return flightAvailableGates;
    }

    public Flight getFlightAt(int index) {
        return scheduleFlights.get(index);
    }

    public List<Flight> getScheduleFlights() {
        return scheduleFlights;
    }

    public FlightGate getFlightGateById(String flightGateId) {
        return id2FlightGate.get(flightGateId);
    }

    public Flight getFlightByFlightId(String flightId) {
        for(Flight f : scheduleFlights) {
            if(f.getFlightId().equals(flightId))
                return f;
        }
        return null;
    }

    public FlightGate getFlightGateAt(int index) {
        return scheduleGates.get(index);
    }

    public List<FlightGate> getScheduleGates() {
        return scheduleGates;
    }

    public List<FlightGate> getNormalGates() {
        return normalGates;
    }

    public List<FlightGate> getAdHocGates() {
        return adHocGates;
    }

    public List<FlightGate> getFlightGatesByIds(Collection<String> gateIds) {
        List<FlightGate> gates = new ArrayList<>();
        for(String gateId : gateIds) {
            gates.add(id2FlightGate.get(gateId));
        }
        return gates;
    }

    public int indexOf(FlightGate gate) {
        return scheduleGates.indexOf(gate);
    }

    public int indexOf(Flight flight) {
        return scheduleFlights.indexOf(flight);
    }

    public Set<String> getRunways() {
        Set<String> runways = new HashSet<>();
        scheduleGates.forEach(gate->{
            runways.add(gate.getRunwayIn());
            runways.add(gate.getRunwayOut());
        });
        return runways;
    }

    public Set<FlightGate> getAttachedAdhocGates(FlightGate gate) {
        if(!gate.isAdHocGate()) {
            if (normalFlightGate2AdHocGate.containsKey(gate)) {
                return normalFlightGate2AdHocGate.get(gate);
            }
        }else{
            if(adHocGate2AdHocGates.containsKey(gate)) {
                return adHocGate2AdHocGates.get(gate);
            }
        }
        return null;
    }

    public String getDate() {
        return date;
    }

    public String toString() {
        return "日期："+date +
                " 该问题机位数量 = "+scheduleGates.size()+"  " +
                "待调度航班数量= "+scheduleFlights.size()+"  " +
                "跑道： "+getRunways();
    }

    // =======================package method ===========================================

    boolean canMerge(Problem problem) {
        for(Flight f1 : problem.scheduleFlights) {
            for(Flight f2 : this.scheduleFlights) {
                if(f1 == f2)
                    return true;
            }
        }
        return false;
    }

    public void merge(Problem problem) {
        Set<FlightGate> gates = new HashSet<>();
        gates.addAll(problem.scheduleGates);
        gates.addAll(this.scheduleGates);
        this.scheduleGates = new ArrayList<>(gates);

        Set<Flight> flights = new HashSet<>();
        flights.addAll(problem.scheduleFlights);
        flights.addAll(this.scheduleFlights);
        this.scheduleFlights = new ArrayList<>(flights);
        this.noRegularGateFlights.addAll(problem.noRegularGateFlights);

        this.normalFlightGate2AdHocGate.putAll(problem.normalFlightGate2AdHocGate);
        this.normalGates.addAll(problem.normalGates);
        this.adHocGates.addAll(problem.adHocGates);
        this.id2FlightGate = new HashMap<>();
        gates.forEach(g->id2FlightGate.put(g.getFlightGateId(),g));

    }

    public boolean isValidProblem() {
        return scheduleFlights.size() > 0 && scheduleGates.size() > 0;
    }

    // ========================private method ===========================================

    private List<Flight> findAirportAndComingFlights(Flight base, IntervalTree<Integer,Flight> intervalTree) {
        List<Flight> conflicts = new ArrayList<>();
        intervalTree.getOverlapping(base).forEach(flight->{
            if(flight != base && ConflictHelper.isBothOccured(base, flight)) {
                conflicts.add(flight);
            }
        });
        return conflicts;
    }

    private double computeFlightGateConflictRate(IntervalTree<Integer,Flight> intervalTree, Flight base,
                                                 Map<String,Double> commonGateMap) {
        List<Flight> conflictFlights = intervalTree.getOverlapping(base);
        double num = 0;
        for(Flight flight : conflictFlights) {
            if(flight != base) {
                String key = base.getFlightId() + flight.getFlightId();
                num += commonGateMap.get(key);
            }
        }
        return num;
    }

    private Map<String,Double> getFlightCompeteGateRate(List<Flight> flights,
                                                        IntervalTree<Integer, Flight> intervalTree,
                                                        Map<Flight, List<FlightGate>> flightAvailableGates) {

        Map<String, Double> map = new HashMap<>();
        for(int i = 0; i < flights.size(); i++) {
            Flight iFlight = flights.get(i);
            Set<FlightGate> iGates = new HashSet<>(flightAvailableGates.get(iFlight));
            List<Flight> conflictFlights = intervalTree.getOverlapping(iFlight);
            for(Flight jFlight : conflictFlights) {
                String key1 = iFlight.getFlightId()+jFlight.getFlightId();
                if(iFlight != jFlight && !map.containsKey(key1)) {
                    String key2 = jFlight.getFlightId()+iFlight.getFlightId();
                    Set<FlightGate> jGates = new HashSet<>(flightAvailableGates.get(jFlight));
                    Set<FlightGate> common = SetUtil.intersect(iGates, jGates);
                    map.put(key1, (common.size()+0.0)/jGates.size());
                    map.put(key2, (common.size()+0.0)/iGates.size());
                }
            }
        }
        return map;
    }
}
